package hebClustering.clusteringAlgorithms;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.IVector;
import hebClustering.vectorSpace.SparseVector;
import hebClustering.vectorSpace.distances.IDistance;

import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import Jama.Matrix;


/**
 *	Implementation of the clustering algorithm Spectral clustering.
 * 
 * 	@see <a href="http://en.wikipedia.org/wiki/Cluster_analysis#Spectral_clustering" target="_blank">Spectral clustering</a>
 */
public class SpectralClustering implements IClusteringAlgorithm {

	int K,I;
	IDistance distance;

	public SpectralClustering(int K,int I, IDistance distance){
		this.K = K;
		this.I = I;
		this.distance = distance;
	}

	@Override
	public ClusterSet cluster(Collection<IVector> dataSet) {
		
		List<IVector> list = new LinkedList<IVector>(dataSet);
		
		Matrix affinity = constructAffinity(list);
		Matrix diagonal = constructDiagonal(affinity);
		Matrix inverseD = inverseSquareRoot(diagonal);

		Matrix L = inverseD.times(affinity).times(inverseD);

		Matrix X = getKLargestEigenVectors(L.eig().getV());

		Matrix Y = renormalizeRows(X);

		HashMap<IVector,Integer> newVectorsToIndex = getNewVectors(Y); 

		IClusteringAlgorithm clusteringAlgorithm = new KMeansPPClustering(K, I, distance); 
		ClusterSet clusters =  clusteringAlgorithm.cluster(newVectorsToIndex.keySet());

		return revertToOldVectors(clusters,list,newVectorsToIndex);
	}

	private ClusterSet revertToOldVectors(ClusterSet set,List<IVector> list,HashMap<IVector, Integer> newVectorsToIndex) {
		ClusterSet newClusterSet = new ClusterSet();
		
		for (Cluster cluster : set){
			Cluster newCluster = new Cluster();
			for (IVector v : cluster){
				newCluster.add(list.get(newVectorsToIndex.get(v)));
			}
			newClusterSet.add(newCluster);
		}
		return newClusterSet;
	}

	private HashMap<IVector,Integer> getNewVectors(Matrix Y) {
		HashMap<IVector,Integer> indexToNewVectors = new HashMap<IVector,Integer>();
		
		for (int i = 0; i < Y.getRowDimension(); i++){
			IVector v = new SparseVector(Y.getRowDimension());
			for (int j = 0; j < Y.getColumnDimension(); j++){
				v.addToVector(j, Y.get(i, j));
			}
			indexToNewVectors.put(v,i);
		}
		
		return indexToNewVectors;
	}

	private Matrix renormalizeRows(Matrix X) {
		Matrix Y = new Matrix(X.getRowDimension(),K);
		double val;
		
		for (int i = 0; i < X.getRowDimension(); i++){
			for (int j = 0; j < K; j++){
				val = X.get(i, j) / Math.pow(squareSumOfRow(X,i),2);
				Y.set(i, j, val);
			}
		}
		
		return Y;
	}
	
	private double squareSumOfRow(Matrix mat,int row){
		double sum = 0.0;
		
		for (int i = 0; i < mat.getColumnDimension(); i++){
			sum += mat.get(row, i);
		}
		
		return sum;
	}

	private Matrix getKLargestEigenVectors(Matrix mat) {
		Matrix resultMatrix = new Matrix(mat.getRowDimension(),K);
		
		double arrRep[][] = mat.transpose().getArrayCopy();
		doubleArrayVector[] arrayVectors = new doubleArrayVector[mat.getRowDimension()];
		
		for (int i = 0; i < arrayVectors.length; i++){
			arrayVectors[i] = new doubleArrayVector(arrRep[i]);
		}
		
		Arrays.sort(arrayVectors,new NormComperator());
		
		for (int i = 0; i < mat.getRowDimension(); i++){
			for (int j = mat.getRowDimension() - K; j < mat.getRowDimension(); j++){
				resultMatrix.set(i, j - (mat.getRowDimension() - K), arrayVectors[j].ithValue(i));
			}
		}
		
		return resultMatrix;
	}

	private Matrix inverseSquareRoot(Matrix diagonal) {
		Matrix resultMatrix = new Matrix(diagonal.getRowDimension(),diagonal.getRowDimension());
		double res;
		
		for (int i = 0; i < diagonal.getRowDimension(); i++){
			res = (double) 1 / (Math.sqrt(diagonal.get(i, i)));
			resultMatrix.set(i,i, res);
		}
		
		return resultMatrix;
	}

	private Matrix constructDiagonal(Matrix affinity) {
		Matrix resultMatrix = new Matrix(affinity.getRowDimension(),affinity.getRowDimension());
		double sum;
		
		for (int i = 0; i < affinity.getRowDimension(); i++){
			sum = 0.0;
			for (int j = 0; j < affinity.getRowDimension(); j++){
				sum += affinity.get(i,j);
			}
			resultMatrix.set(i,i,sum);
		}
		
		return resultMatrix;
	}

	private Matrix constructAffinity(List<IVector> dataSet) {
		Matrix resultMatrix = new Matrix(dataSet.size(),dataSet.size());
		double sigma = 1.0 / Math.sqrt(Math.E);

		for (int i = 0; i < dataSet.size(); i++){
			for (int j = 0; j < dataSet.size() && j <= i; j++){
				double res;
				if (i == j){
					res = 0;
					resultMatrix.set(i, i, res);
				}else{
					res = Math.exp(-Math.pow(distance.calc(dataSet.get(i), dataSet.get(j)),2)/(2*sigma*sigma));
					resultMatrix.set(i, j, res);
					resultMatrix.set(j, i, res);
				}
			}
		}

		return resultMatrix;
	}
	
	private class NormComperator implements Comparator<doubleArrayVector>{

		@Override
		public int compare(doubleArrayVector o1, doubleArrayVector o2) {
			return (int) (euclidianNorm(o1.getArray()) - euclidianNorm(o2.getArray()));
		}
		
		private double euclidianNorm(double[] a){
			double res = 0;
			
			for (int i = 0; i < a.length; i++){
				res += Math.pow(a[i],2);
			}
			
			return Math.sqrt(res);
		}
		
	}
	
	private class doubleArrayVector {
		private double[] arr;
		
		public doubleArrayVector(double[] arr){
			this.arr = arr;
		}
		
		public double[] getArray(){
			return arr;
		}
		
		public double ithValue(int i){
			return arr[i];
		}
	}

}
